home *** CD-ROM | disk | FTP | other *** search
/ Turnbull China Bikeride / Turnbull China Bikeride - Disc 2.iso / STUTTGART / LANG / PROLOG / BP330 / !BinPro330 / progs / lfibo < prev    next >
Text File  |  1993-09-05  |  1KB  |  40 lines
  1. :-write('Program: lfibo.pl'),nl.
  2. :-write('Author: Paul Tarau'),nl.
  3. :-write('fibonacci(40) program with constant time lemmas'),nl.
  4. :-write('executed 10000 times'),nl.
  5.  
  6. go:-
  7.         I=10000,N=40,
  8.         statistics(runtime,_),
  9.         statistics(global_stack,[H1,_]),
  10.         statistics(trail,[TR1,_]),
  11.         f_iter(I,N,R),
  12.         statistics(runtime,[_,T]),
  13.         statistics(global_stack,[H2,_]),
  14.         statistics(trail,[TR2,_]),
  15.         H is H2-H1,TR is TR2-TR1,
  16.         bb,
  17.         write([time=T,heap=H,trail=TR,fibo(N,R)]),nl.
  18.  
  19. range(Min,Min,Max):-Min=<Max.
  20. range(I,Min,Max):-
  21.         Min<Max,
  22.         Min1 is Min+1,
  23.         range(I,Min1,Max).
  24.         
  25. f_iter(Max,N,R):-range(_,1,Max),fibo(N,R),fail.
  26. f_iter(_,N,R):-fibo(N,R).
  27.  
  28. fibo(N,1):-N<2,!.
  29. fibo(N,Y):-
  30.     N1 is N-1, N2 is N-2,
  31.     fibo_lemma(fibo,N1,Y1),
  32.     fibo_lemma(fibo,N2,Y2),
  33.     Y is Y1+Y2.
  34.  
  35. % optimized lemma: <P,I> --> X (P,I,O must be atomic)
  36. fibo_lemma(P,I,O):-val(P,I,X),!,X=O.
  37. fibo_lemma(P,I,O):-functor(G,P,2),arg(1,G,I),G,!,
  38.     arg(2,G,O),
  39.     def(P,I,O).
  40.